slope trick 2
의식의 흐름(정리 다 하면 삭제될 예정)
tag:slope를 밀다보니 슬로프트릭1 게시글의 내용만으로는 못푸는게 있어서 더 공부한 내용을 정리한다.
이전에 설명한 슬로프트릭은 최솟값 기준으로 기울기 증감위치를 저장하는 방식이었다. 1편에서도 잠깐 언급되었지만 기울기 업데이트가 굉장히 클때 o(delta)이므로 비효율적이다. 자기자신을 평행이동한 그래프를 더하는 작업도 o(size)로 비효율적이다. 그래프의 Domain범위가 크지 않다면 굳이 증감위치를 저장하지 말고, 각 위치x별로 이전위치x-1의 값과의 증감(=slope)을 저장해보자. 볼록한 함수에 대해 그 차이값(=미분값?차분값?)을 저장하기 때문에 일종의 도함수를 저장하는거로 볼 수 있고, 이는 볼록함수의 도함수이므로 증가함수가 된다. [TODO:설명 이어서 하기].
이렇게 표현한 슬로프트릭을 diff슬로프트릭이라 하고 슬로프트릭1에서 표현한걸 pos슬로프트릭이라고 하자. diff표현은 pos표현과는 다르게 domain크기에 제약이 생긴다. 너무 넓으면 저장할 diff개수가 많아지기 때문. 대신 diff슬로프트릭은 그래프의 특정지점을 한칸 쉬프트하고 +delta하는걸 pq.push(delta)로 표현할 수 있다. 다만, 이는 연산이 concavity를 보존할때만 가능한데, 그 성질이 보존된다는건 다시 concave하다는것이므로, concave성질에 의해 delta를 정렬된상태로 추가할 수 밖에 없고 원래 원하는 연산도 "특정지점"이 어디인지 몰라도 [연산해도 볼록성이 보존]된다는 사실과[쉬프트후 증가시킬 +delta]를 알기만 하면 그냥 push(delta)해주면 된다는 것이다.
위 내용을 일반화해서, 볼록성이 보존되는 연산이면서 임의크기 쉬프트와 임의크기 델타를 하는 연산은 map만으로는 부족할거같다. "델타/쉬프트량"으로 기울기를 알 수 있으므로 해당되는 기울기에 맞는 위치로 가서 추가해줘야하는데, 해당되는 기울기를 찾으려면 map은 기울기가 아니라 "기울기의 변화지점=(미분의 미분)"을 저장하는거다보니 누적합도 필요하고 좀 더러운 자료구조문제가 되는것같다.
쓰다보니 정리된 생각: 1에서 설명한건 [기울기의 변화=이계도함수]를 저장해 나타낸거고 2에서 설명한건 direct하게 [기울기=도함수]를 저장한 슬로프트릭이다. 각각을 2계슬로프 1계슬로프라고 부르겠다. 1계슬로프는 1차함수 더하는 연산이 효율적일 수 없다. 왜냐하면 모든 기울기가 변화하기 때문에. 그러나 2계슬로프로는 가능하다. 왜냐하면 2계표현의 하나만 업데이트해도 나중에 누적합하여 1계표현(기울기)을 구하면 특정지점 이후로 특정값만큼 전부 증가하기 때문이다. imos법과 Fenwick Range Update Point Query를 생각하면 이해하는데 도움이 될듯. 이번에는 1차함수가 아니라 상수함수를 더하는 것을 생각해보자. 이 경우 2계슬로프로는 처리할 수가 없다. 왜냐하면 2계미분값의 변화는 1차함수(ax+b and a!=0)형태의 변화만 일어나기 때문이다. 그러나 1계슬로프의 한 값을 변화시키면 그 위치 이후로의 함수값들 전부 변화량만큼 변화한다. 방금전에는 기울기의 Range Update였다면 이번에는 값의 Range Update를 하는 것이다. 그렇기 때문에 값의 미분인 기울기의 변화를 통해 처리할 수 있다. 2계슬로프 구현은 슬로프트릭1에서 다뤘고, 1계슬로프 구현은 좀 tricky한 부분이 있는거같다. 어떤 기울기 x[i]를 업데이트할 때, 볼록성이 깨지지 않으려면 x[i-1]보다 크고 x[i+1]보다는 작은 값이어야 한다는 특징이 있다. 즉, 기울기는 위치로 정렬하던 값으로 정렬하던 순서가 같으므로 PQ로 관리해주면서 push(z)했을때의 의미는 기울기가 z보다 큰것들은 평행이동(+1,+z) 시킨 후 +1때문에 생긴 빈공간i에는 f(i-1)+z으로 채우게 된다. 1계슬로프 연산은 뭔가 굉장히 specific한 느낌(min(f(i-1),f(i)+k) 이런 (1,k) 평행이동형태)이라 dp점화식의 형태가 좀 제한적일것 같다. 아마도 mincowski sum형태(=평행이동)만 가능해서 parklife해설에 언급된거일듯?(읽을당시에는 왜 나온건지 이해불가능이었음) 1계슬로프에서는 최종적으로 trivial한 끝쪽 함수값에서 기울기누적해서 목표함수값 계산하는듯. 자세한건 문제풀면서 이해하자.
이차함수($ax^2+bx+c$)도 모든 이차함수의 a값이 같으면 일차함수같은 성질(미지수가 2개이므로 자유도가 2이고, 두 서로다른 함수의 교점이 하나로 유일하고 등등)이 있어서 어떻게 cost가 a값이 같은 이차함수들인 슬로프트릭 variation이 있는듯? BOJ16601과 BOJ20965 이 문제들이 그런거같음. 20965의 공식솔루션에서 설명해주고 있으니 관심있으면 읽어보자.
유형4
$\left|x-3\right|+\left|x+3\right|+\left|x-2\right|+\left|3x+3\right|$ 와 그 (1,3)평행이동 $\left|\left(x-1\right)-3\right|+\left|\left(x-1\right)+3\right|+\left|\left(x-1\right)-2\right|+\left|3\left(x-1\right)+3\right|+3$를 관찰해보자. min취하면 x=2~3 부분이 볼록성 깨지는거 같아보이지만 정수에 대해서만 그래프를 사용하기 때문에 볼록성은 유지된다고 볼 수 있다. 대신 기존 그래프의 기울기집합에 기울기3을 추가한 형태가 된다. 이는 일반화해서 평행이동(1,k)에 대해 기울기 k를 집합에 추가하는것과 동일하다고 할 수 있다. 평행이동을 (2,3)으로 변경해보면 일단 기울기자체가 분수가 되서 망했고, 심지어 x축 1만큼 이동할때는 정수만 사용해서 괜찮았지만 2이상움직인다면 그사이에 정수가 포함되기 때문에 값의 볼록성이 깨져버린다! 한번에 두칸$min(f(x),f(x-2)+2p)$는 볼록성이 깨지지만 다행히도 연속된 한칸씩$min(f(x),f(x-1)+p,f(x-2)+2p)$는 볼록성이 유지된다. 이때 두번의 평행이동의 기울기도 동일해야 볼록성이 유지된다는거에 주의하자. 평행이동의 기울기가 볼록(기울기front<기울기back)($min(f(x),f(x-1)+p,f(x-2)+2p+n)$)일때도 될거같은데 확신은 없다
NOTE: 이 연속된 직선평행이동의 극단케이스가 유형3(Fireworks)이다. 유형3은 기존값들이 전부 무한히 멀리 날라가버려 상관없고 그곳에 평행이동기울기 직선하나 추가되는거라 2차슬로프로 해결가능했다.
Buy Low Sell High
f(x,y)=x일에 주식y개를 가지고 있을때 최대잔고
$f(x,y)=max(f(x-1,y-1)-p[x],f(x-1,y),f(x-1,y+1)+p[x])$
$f(x-1,y)$가 평행이동$(1,-p[x])$와 평행이동$(-1,p[x])$을 한 형태이고 기울기는 둘다 -p[x]이므로 -p[x]를 두번 넣어주면 된다.
정렬된 기울기 순서대로 -i,-i+1,...,0,1,...,i 이런 번호를 매겨야 하기 때문에 시작인덱스를 관리해줘야 한다. 이 문제에서는 2개를 추가하면 인덱스-1이 추가되는데, 음수인덱스는 음수stock개수를 의미하므로 pop하여 음수번호인걸 아예 제거하기때문에 상관없다. USACO Guide에 TODO로 나온 문제(음수stock가능해짐)은 인덱스관리로 풀어야할듯.
n일까지 관리해준 다음 f(n,0)을 구해야 하는데, 양쪽 극단값(전부다 사거나 전부다 팔거나)을 구한다음 기울기타고 0까지 내려오면 답이 된다. 다만 여기서 전부다 팔아버리는 극단값은 stock개수가 음수가 되서 사용할수 없으므로, 전부다 사는거를 base로 해야한다.
https://codeforces.com/contest/866/submission/141353687 그리디(옵션개념)
https://codeforces.com/contest/866/submission/141436477 1계슬로프
유형5
TODO: $ax^2+bx+c$에서 a가 고정된 cost함수로 slope trick하는 방법